package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 216. 组合总和 III
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 21:21
 */
public class E216 {
    private final int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}; // 1~9

    /**
     * <h3>递归加dfs，回溯剪枝</h3>
     * @param k 从1-9选k个
     * @param n k个数和的目标值
     * @return 所有符合要求的组合
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, result, new LinkedList<>(), k, n);
        return result;
    }

    /**
     * 递归函数实现，这里不需要用visited布尔数组，因为不会发生回头的情况
     * @param start 当前递归对应位置的有可能数字遍历的起始位置，因为不能回头走，否则会出现重复集
     * @param result 存储符合要求的结果集
     * @param currentCombine 当前递归中存储的组合
     * @param k 从1-9选k个
     * @param n k个数和的目标值
     */
    private void dfs(int start,
                     List<List<Integer>> result,
                     LinkedList<Integer> currentCombine,
                     int k,
                     int n) {
        // 递归终止条件：当前组合的长度等于k，并且目标值等于0，说明已经选取到了目标值，那么就加入到结果集中，然后返回
        if (currentCombine.size() == k && n == 0){
            result.add(new ArrayList<>(currentCombine));
            return;
        }
        // 依次尝试start - nums.length之间的每一个可能放在当前位置的数字
        for (int i = start; i < nums.length; i++){
            if (n - nums[i] < 0) break; // 如果当前位置的当前遍历到的数字入选后，如果剩余目标值小于0了，那么后面的就没必要选入了，所以直接进行剪枝
            currentCombine.push(nums[i]); // 选取当前位置的数字
            dfs(i + 1, result, currentCombine, k, n - nums[i]); // 递归选取下一个位置的数字
            currentCombine.pop(); // 回溯
        }
    }
}
